GATE IT 2005


Q11.

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is
GateOverflow

Q12.

Let L be a regular language and M be a context-free language, both over the alphabet \Sigma. Let L^c and M^c denote the complements of L and M respectively. Which of the following statements about the language L^c\cup M^c is TRUE?
GateOverflow

Q13.

The language \{0^n 1^n 2^n \mid 1 \leq n \leq 10^6\} is
GateOverflow

Q14.

Two shared resources R_1 and R_2 are used by processes P_1 and P_2. Each process has a certain priority for accessing each resource. Let T_{ij} denote the priority of P_i for accessing R_j. A process P_i can snatch a resource R_k from process P_j if T_{ik} is greater than T_{jk}. Given the following : (I). T_{11} \gt T_{21} (II). T_{12} \gt T_{22} (III). T_{11} \lt T_{21} (IV). T_{12} \lt T_{22} Which of the following conditions ensures that P_1 and P_2 can never deadlock?
GateOverflow

Q15.

Consider the entities 'hotel room', and 'person' with a many to many relationship 'lodging' as shown below:If we wish to store information about the rent payment to be made by person (s) occupying different hotel rooms, then this information should appear as an attribute of
GateOverflow

Q16.

Let f be a function from a set A to a set B, g a function from B to C, and h a function from A to C, such that h(a) = g(f(a)) for all a \in A. Which of the following statements is always true for all such functions f and g?
GateOverflow

Q17.

In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is
GateOverflow

Q18.

In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity. \begin{array}{|ll|ll|}\hline \text{1.} & \text{Bellman-Ford algorithm} & \text{A:} & \text{$O(m\log n)$} \\\hline \text{2.} & \text{Kruskal's algorithm} & \text{B:}& \text{$O(n^3)$} \\\hline \text{3.}& \text{Floyd-Warshall algorithm} & \text{C:} & \text{$O(nm)$} \\\hline \text{4.} & \text{Topological sorting} &\text{D:} & \text{$O(n+m)$} \\\hline \end{array}
GateOverflow

Q19.

The circuit shown below implements a 2-input NOR gate using two 2-4 MUX (control signal 1 selects the upper input). What are the values of signals x, y and z?
GateOverflow

Q20.

A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted?
GateOverflow